package main

type Node struct {
	Val      int
	Children []*Node
}

func postorder(root *Node) []int {
	if root == nil {
		return []int{}
	}
	if root.Children == nil || len(root.Children) == 0 {
		return []int{root.Val}
	}
	var result []int
	for _, v := range root.Children {
		ret := postorder(v)
		result = append(result, ret...)
	}
	result = append(result, root.Val)
	return result
}

type MyNode struct {
	n       *Node
	visited bool
}

func postorder2(root *Node) []int {
	if root == nil {
		return []int{}
	}
	if root.Children == nil || len(root.Children) == 0 {
		return []int{root.Val}
	}
	stack := []*MyNode{
		{n: root, visited: false},
	}
	var result []int
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[0 : len(stack)-1]
		if top.visited {
			result = append(result, top.n.Val)
		} else {
			stack = append(stack, &MyNode{n: top.n, visited: true})
			if top.n.Children != nil && len(top.n.Children) > 0 {
				children := top.n.Children
				for i := len(children) - 1; i >= 0; i-- {
					v := children[i]
					stack = append(stack, &MyNode{n: v, visited: false})
				}
			}

		}
	}
	return result
}

func main() {
	n0 := &Node{Val: 0}
	n1 := &Node{Val: 3}
	n2 := &Node{Val: 2}
	n3 := &Node{Val: 4}
	n4 := &Node{Val: 5}
	n5 := &Node{Val: 6}
	n0.Children = []*Node{n1, n2, n3}
	n1.Children = []*Node{n4, n5}
	ret := postorder2(n0)
	println(ret)
}
